//
//  sort.cpp
//  learnC++
//
//  Created by apple on 2018/5/28.
//  Copyright © 2018年 yunfan.com. All rights reserved.
//

#include "sort.hpp"


void test_sort(){
    
    //选择排序
//    select_sort();
    
//    select_cpp_sort();
    
    bubble_sort();
}

void select_sort(){
    const int length = 5;
    int array[length] = {30, 50, 20, 10, 40};
    
    //直接遍历所有一个个比较找最小的index，然后交换
    // Step through each element of the array
    // (except the last one, which will already be sorted by the time we get there)
    for (int startIndex = 0; startIndex < length - 1; ++startIndex)
    {
        // smallestIndex is the index of the smallest element we’ve encountered this iteration
        // Start by assuming the smallest element is the first element of this iteration
        int smallestIndex = startIndex;
        
        // Then look for a smaller element in the rest of the array
        for (int currentIndex = startIndex + 1; currentIndex < length; ++currentIndex)
        {
            // If we've found an element that is smaller than our previously found smallest
            if (array[currentIndex] < array[smallestIndex])
                // then keep track of it
                smallestIndex = currentIndex;
        }
        
        // smallestIndex is now the smallest element in the remaining array
        // swap our start element with our smallest element (this sorts it into the correct place)
        std::swap(array[startIndex], array[smallestIndex]);
    }
    
    for (int index = 0; index < length; ++index)
        std::cout << array[index] << ' ';
}

void select_cpp_sort(){
    
    int array[5] = {30,50,20,10,40};
    
    int length = sizeof(array)/sizeof(array[0]);
    
    //传起始位置和末位置
    std::sort(array, array+length);
    
    
    for (int i = 0; i < length; ++i) {
        std::cout << array[i] << ' ';
    }
    
}

void bubble_sort(){
    int array[] = { 6, 3, 2, 9, 7, 1, 5, 4, 8 };
    const int length = sizeof(array) / sizeof(array[0]);
    // Step through each element of the array except the last
    for (int iteration = 0; iteration < length-1; ++iteration)
    {
        // Search through all elements up to the end of the array - 1
        // The last element has no pair to compare against
        for (int currentIndex = 0; currentIndex < length - 1; ++currentIndex)
        {
            // If the current element is larger than the element after it, swap them
            if (array[currentIndex] > array[currentIndex+1])
                std::swap(array[currentIndex], array[currentIndex + 1]);
        }
    }
    
    // Now print our sorted array as proof it works
    for (int index = 0; index < length; ++index)
        std::cout << array[index] << ' ';
    
}
